package List;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-02-27
 * Time:14:11
 * Text：143.重排链表
 */
public class Text3 {

    public void reorderList(ListNode head) {
        ListNode l=head;   //表示中间结点
        ListNode r=head;
        while(r!=null && r.next!=null){
            l=l.next;
            r=r.next.next;
        }
        r=l.next;
        l.next=null;
        l=head;
        ListNode newHead=new ListNode();  //逆序之后的新节点
        //逆序后半部分
        while(r!=null){
            ListNode text=r.next;
            r.next=newHead.next;
            newHead.next=r;
            r=text;
        }
        r=newHead;
        ListNode code=new ListNode();
        ListNode recode=code;

        while(l!=null || r!=null){
            if(l!=null){
                recode.next=l;
                recode=recode.next;
                l=l.next;
            }
            if(r!=null){
                recode.next=r;
                recode=recode.next;
                r=r.next;
            }
        }
        head=code.next;
    }
}
